package treePackage;

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import parser.Block;

public class Tree {

	private Node root;
	private Map<String, Block> blocks;
	private StringBuffer polishExpression;

	public Tree(Map<String, Block> blocks) {
		this.blocks = blocks;
		this.root = new Node(null, null, null);
		this.polishExpression = new StringBuffer();
		convertToTree(this.blocks, root);
		convertTreeToExpression(root);
	}

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}

	public StringBuffer getPolishExpression() {
		return polishExpression;
	}

	private static Map<String, Block> sortByComparator(
			Map<String, Block> unsortMap) {

		List<Block> list = new LinkedList<Block>(unsortMap.values());

		// sort list based on comparator
		Collections.sort(list, new Comparator<Block>() {
			public int compare(Block o1, Block o2) {
				if (o1.getX_coordinate() < o2.getX_coordinate())
					return -1;
				else if (o1.getX_coordinate() > o2.getX_coordinate())
					return 1;
				else if (o1.getY_coordinate() < o2.getY_coordinate())
					return -1;
				else if (o1.getY_coordinate() > o2.getY_coordinate())
					return 1;
				else
					return 0;
			}
		});

		// put sorted list into map again
		Map<String, Block> sortedMap = new LinkedHashMap<String, Block>();
		for (Iterator<Block> it = list.iterator(); it.hasNext();) {
			Block entry = it.next();
			sortedMap.put(entry.getBlockName(), entry);
		}
		return sortedMap;
	}

	private void convertToTree(Map<String, Block> blocks, Node tree) {

		if (blocks == null)
			return;

		Map<String, Block> sortedMap = sortByComparator(blocks);
		FloorplanSlice result = find_slice(sortedMap);

		if (result == null) {
			// System.out.println("Somthing is wrong in Tree.java line 42\n");
			return;
		}

		if (result.getType() == SliceType.VERTICAL)
			tree.setValue("V");

		else
			tree.setValue("H");

		tree.setLeft_son(new Node(null, null, null));
		tree.setRight_son(new Node(null, null, null));

		if (result.getLeftBlockGroup().size() == 1
				&& result.getRightBlockGroup().size() == 1) {
			tree.getLeft_son().setValue(
					result.find_name(result.getLeftBlockGroup()));
			tree.getRight_son().setValue(
					result.find_name(result.getRightBlockGroup()));
			return;
		}

		if (result.getRightBlockGroup().size() == 1) {
			tree.getRight_son().setValue(
					result.find_name(result.getRightBlockGroup()));
			convertToTree(result.getLeftBlockGroup(), tree.getLeft_son());
			return;
		}

		if (result.getLeftBlockGroup().size() == 1) {
			tree.getLeft_son().setValue(
					result.find_name(result.getLeftBlockGroup()));
			convertToTree(result.getRightBlockGroup(), tree.getRight_son());
			return;
		}

		convertToTree(result.getLeftBlockGroup(), tree.getLeft_son());
		;
		convertToTree(result.getRightBlockGroup(), tree.getRight_son());
	}

	private FloorplanSlice find_slice(Map<String, Block> blocks) {

		double verticalCutLineCoor, horizontalCutLineCoor;

		verticalCutLineCoor = findVerticalCutLine(blocks);
		if (verticalCutLineCoor != -1) {
			Map<String, Block> leftBlocks = new HashMap<String, Block>();
			Map<String, Block> rightBlocks = new HashMap<String, Block>();

			for (Block block : blocks.values()) {
				if (block.getX_coordinate() < verticalCutLineCoor)
					leftBlocks.put(block.getBlockName(), block);
				else
					rightBlocks.put(block.getBlockName(), block);
			}
			if (rightBlocks.size() != 0) {
				FloorplanSlice result = new FloorplanSlice(SliceType.VERTICAL,
						leftBlocks, rightBlocks);
				return result;
			}
		}

		horizontalCutLineCoor = findHorizontalCutLine(blocks);
		if (horizontalCutLineCoor != -1) {
			Map<String, Block> aboveBlocks = new HashMap<String, Block>();
			Map<String, Block> belowBlocks = new HashMap<String, Block>();

			for (Block block : blocks.values()) {
				if (block.getY_coordinate() > horizontalCutLineCoor)
					aboveBlocks.put(block.getBlockName(), block);
				else
					belowBlocks.put(block.getBlockName(), block);
			}
			if (aboveBlocks.size() != 0) {
				FloorplanSlice result = new FloorplanSlice(
						SliceType.HORIZONTAL, aboveBlocks, belowBlocks);
				return result;
			}
		}
		return null;
	}

	// Trying to find a vertical cut line, returns -1 if not found
	// otherwise it returns coordinate of the vertical cut line
	private static double findVerticalCutLine(Map<String, Block> blocks) {

		double block1RightCoor;
		int flag = 0;

		for (Block block1 : blocks.values()) {
			block1RightCoor = block1.getX_coordinate()
					+ (block1.getHorizontalLength() / 2);
			flag = 0;
			for (Block block2 : blocks.values()) {
				double block2LeftCoor = block2.getX_coordinate()
						- (block2.getHorizontalLength() / 2);
				double block2RightCoor = block2.getX_coordinate()
						+ (block2.getHorizontalLength() / 2);
				if (block2LeftCoor < block1RightCoor
						&& block1RightCoor < block2RightCoor) {
					flag = 1;
					break;
				}
			}
			if (flag == 0) {
				double verticalCutLineCoor = block1.getX_coordinate()
						+ (block1.getHorizontalLength() / 2);
				Map<String, Block> leftBlocks = new HashMap<String, Block>();
				Map<String, Block> rightBlocks = new HashMap<String, Block>();

				for (Block block : blocks.values()) {
					if (block.getX_coordinate() < verticalCutLineCoor)
						leftBlocks.put(block.getBlockName(), block);
					else
						rightBlocks.put(block.getBlockName(), block);
				}
				if (rightBlocks.size() != 0) {
					return verticalCutLineCoor;
				}
			}
		}
		return -1;
	}

	// Trying to find a horizontal cut line, returns -1 if not found
	// otherwise it returns coordinate of the horizontal cut line
	private static double findHorizontalCutLine(Map<String, Block> blocks) {

		double block1HeightCoor;
		int flag = 0;

		for (Block block1 : blocks.values()) {
			block1HeightCoor = block1.getY_coordinate()
					+ (block1.getVerticalLength() / 2);
			flag = 0;
			for (Block block2 : blocks.values()) {
				double block2LowCoor = block2.getY_coordinate()
						- (block2.getVerticalLength() / 2);
				double block2HeightCoor = block2.getY_coordinate()
						+ (block2.getVerticalLength() / 2);
				if (block2LowCoor < block1HeightCoor
						&& block1HeightCoor < block2HeightCoor) {
					flag = 1;
					break;
				}
			}
			if (flag == 0) {
				double horizontalCutLineCoor = block1.getY_coordinate()
						+ (block1.getVerticalLength() / 2);
				Map<String, Block> aboveBlocks = new HashMap<String, Block>();
				Map<String, Block> belowBlocks = new HashMap<String, Block>();

				for (Block block : blocks.values()) {
					if (block.getY_coordinate() > horizontalCutLineCoor)
						aboveBlocks.put(block.getBlockName(), block);
					else
						belowBlocks.put(block.getBlockName(), block);
				}
				if (aboveBlocks.size() != 0) {
					return horizontalCutLineCoor;
				}
			}
		}
		return -1;
	}

	private void convertTreeToExpression(Node tree) {

		if (tree == null)
			return;

		convertTreeToExpression(tree.getLeft_son());
		convertTreeToExpression(tree.getRight_son());
		polishExpression.append(tree.getValue());

	}

}
